package org.cy.algorithm.chapter_06;

import org.cy.algorithm.util.AlgorithmUtil;

import java.util.Arrays;

public class Heap_6_2_5 {

    // 使用循环维持大顶堆
    public void heapifyWithLoop(int[] arr, int i) {
        do {
            int left = 2 * i;
            int right = 2 * i + 1;
            int largest = i;
            if (left < arr.length && arr[left] > arr[largest]) {
                largest = left;
            }
            if (right < arr.length && arr[right] > arr[largest]) {
                largest = right;
            }
            if (largest != i) {
                AlgorithmUtil.swap(arr, i, largest);
                i = largest;
            } else {
                // 退出
                break;
            }
        } while (i * 2 < arr.length);
    }

    public void buildHeap(int[] arr) {
        for (int i = arr.length / 2; i >= 0; i--) {
            maxHeapify(arr, i);
        }
    }

    // 使用循环维持大顶堆
    public void maxHeapify(int[] arr, int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int largest = i;
        if (left < arr.length && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < arr.length && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            AlgorithmUtil.swap(arr, i, largest);
            maxHeapify(arr, largest);
        }
    }

    public static void main(String[] args) {
        Heap_6_2_5 h = new Heap_6_2_5();
        for (int i = 0; i < 10000; i++) {
            int[] arr = AlgorithmUtil.createRandomArray(100);
            int[] recuse = AlgorithmUtil.copyArray(arr);
            int[] loop = AlgorithmUtil.copyArray(arr);
            h.maxHeapify(recuse, 3);
            h.heapifyWithLoop(loop, 3);
            if (!Arrays.equals(recuse, loop)) {
                System.out.println("Oops");
                return;
            }
        }
        System.out.println("OK");
    }
}
